package com.utility;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Array {

	public static <T> void swap(T[] A, int i, int j){
		T temp=A[i];
		A[i]=A[j];
		A[j]=temp;
	}
	
	public static int median(int[] A,int l,int h){
		int mid = l+(h-l)/2;
		if(A[mid]>=A[h]){
			if(A[mid]<=A[l])
				return mid;
			else if(A[h]>A[l])
				return h;
		}
		else
		{
			if(A[mid]>=A[l])
				return mid;
			else if(A[l]>A[h])
				return h;
		}
		return l;
	}
	
	public int findMax(int[] A){
		int max=Integer.MIN_VALUE;
		for(int i=0;i<A.length;i++)
			if(A[i]>max)
				max=A[i];
		return max;
	}
	
	public int findMin(int[] A){
		int min=Integer.MAX_VALUE;
		for(int i=0;i<A.length;i++)
			if(A[i]<min)
				min=A[i];
		return min;
	}
	public int median(int[] A,int K){
		
		return median(A,K,findMin(A),findMax(A),(A.length+1)/2-1,A.length);
	}
	
	public int countNumbers(int[] A, int lInc, int rInc){
		int len=A.length;
		int count=0;
		for(int i=0;i<len;i++){
			if(A[i]>=lInc && A[i]<=rInc)
				count++;
		}
		return count;
	}
	
	public int findNum(int[] A, int l, int r,int pos){
		//Extra 3log3 overhead max??
		int len=A.length;
		int i=0;
		List<Integer> ll=new ArrayList<Integer>();
		for(i=0;i<len;i++){
			if(A[i]>=l && A[i]<=r)
				ll.add(A[i]);
		}
		Collections.sort(ll);
		return ll.get(pos);
	}
	public int median(int[] A, int K, int lInc, int rInc,int medianPos,int N){
		if(N<=K){
			if(K<=3)
				return findNum(A,lInc,rInc,medianPos);
			K=K/2;
			return median(A,K,lInc,rInc,medianPos,N);
		}
		int size=rInc-lInc+1;
		int boxSize=size/K;
		int prevCount=0;
		int curCount=0;
		int l=lInc;
		for(int i=0;i<K;i++){
			prevCount=curCount;
			curCount+=countNumbers(A,l,l+boxSize);
			if(curCount>medianPos)
				break;
			l=l+boxSize+1;
			
		}
		return median(A, K, l,l+boxSize ,medianPos-prevCount,curCount-prevCount);
	}
}
